package com.github.kilianB.datastructures.tree;

import java.io.Serializable;
import java.util.List;
import java.util.PriorityQueue;

import com.github.kilianB.datastructures.tree.binaryTree.Leaf;
import com.github.kilianB.datastructures.tree.binaryTree.Node;
import com.jstarcraft.dip.hash.Hash;

/**
 * @author Kilian
 *
 */
public abstract class AbstractBinaryTree<T> implements Serializable {

	private static final long serialVersionUID = 8698935405804461236L;

	/**
	 * The root node of the tree.
	 */
	protected Node root;

	/**
	 * Keep track of how many hashes were added to the tree
	 */
	protected int hashCount;

	/**
	 * Flag indicating if hashes origin should be checked
	 */
	protected boolean ensureHashConsistency;
	/**
	 * The algorithm id all hashes have to match if they want to perform an action
	 */
	protected int algoId;

	/**
	 * 
	 * @param ensureHashConsistency If true adding and matching hashes will check
	 *                              weather they are generated by the same
	 *                              algorithms as the first hash added to the tree
	 * 
	 */
	public AbstractBinaryTree(boolean ensureHashConsistency) {
		root = new Node();
		this.ensureHashConsistency = ensureHashConsistency;
	}

	protected AbstractBinaryTree() {
	}

	/**
	 * Insert a value associated with the supplied hash in the binary tree (similar
	 * to a map). Saved values can be found by invoking
	 * {@link #getElementsWithinHammingDistance}.
	 * <p>
	 * 
	 * Nodes which do not exist will be created. Please be aware that similar to
	 * comparing different hashes for images only hashes produced by the same
	 * algorithms will return useable results.
	 * <p>
	 * 
	 * If the tree is configured to ensureHashConsistency this function will throw
	 * an unchecked IlleglStateException if the added hash does not comply with the
	 * first hash added to the tree.
	 * 
	 * @param hash  The hash used to save the value in the tree
	 * @param value The value which will be returned if the hash . Common values
	 *              point to the image used to create the hash or an id in a SQL
	 *              table
	 * 
	 */
	@SuppressWarnings("unchecked")
	protected void addHash(Hash hash, T value) {

		if (ensureHashConsistency) {
			if (algoId == 0) {
				algoId = hash.getAlgorithmId();
			} else {

				if (algoId != hash.getAlgorithmId())
					throw new IllegalStateException("Tried to add an incompatible hash to the binary tree");
			}
		}

		// TODO create test case hash with only 0's is too long
		Node currentNode = root;

		for (int i = hash.getBitResolution() - 1; i > 0; i--) {
			boolean bit = hash.getBitUnsafe(i);
			Node tempNode = currentNode.getChild(bit);
			if (tempNode == null) {
				currentNode = currentNode.createChild(bit);
			} else {
				currentNode = tempNode;
			}
		}
		// We reached the end
		boolean bit = hash.getBit(0);
		Node leafNode = currentNode.getChild(bit);
		Leaf<T> leaf;
		if (leafNode != null) {
			leaf = (Leaf<T>) leafNode;
		} else {
			leaf = (Leaf<T>) currentNode.setChild(bit, new Leaf<T>());
		}
		leaf.addData(value);
		hashCount++;
	}

	/**
	 * @return the root of the binary tree
	 */
	public Node getRoot() {
		return root;
	}

	/**
	 * @return how many hashes were added to the tree
	 */
	public int getHashCount() {
		return hashCount;
	}

	/**
	 * Traverse the tree and output all key = hashes and values found.
	 */
	public void printTree() {
		printTree(root, "");
	}

	/**
	 * Return all elements of the tree whose hamming distance is smaller or equal
	 * than the supplied max distance.
	 * 
	 * If the tree is configured to ensureHashConsistency this function will throw
	 * an unchecked IlleglStateException if the checked hash does not comply with
	 * the first hash added to the tree.
	 * 
	 * @param hash        The hash to search for
	 * @param maxDistance The maximal hamming distance deviation all found hashes
	 *                    may possess. A distance of 0 will return all objects added
	 *                    whose hash is exactly the hash supplied as the first
	 *                    argument
	 * 
	 * @return Search results contain objects and distances matching the search
	 *         criteria. The results returned are ordered to return the closest
	 *         match first.
	 */
	public abstract PriorityQueue<Result<T>> getElementsWithinHammingDistance(Hash hash, int maxDistance);

	/**
	 * Get the most similar to the queried argument. In case of equidistant hashes,
	 * multiple objects may be returned.
	 * 
	 * @param hash the hash to search the closest match for
	 * 
	 * @return the hash the most similar to the supplied hash
	 */
	public abstract List<Result<T>> getNearestNeighbour(Hash hash);

	/**
	 * Recursively traverse the tree and print all hashes found
	 * 
	 * @param n         The current node whose children will be looked at
	 * @param curString The current hash this node represents
	 */
	@SuppressWarnings("unchecked")
	private void printTree(Node n, String curString) {

		if (n instanceof Leaf) {
			System.out.println("Leaf found: " + curString + " " + ((Leaf<T>) n).getData());
		} else {

			if (n.leftChild != null) {
				printTree(n.leftChild, curString + "1");
			}
			if (n.rightChild != null) {
				printTree(n.rightChild, curString + "0");
			}
		}
	}

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + algoId;
		result = prime * result + (ensureHashConsistency ? 1231 : 1237);
		result = prime * result + hashCount;
		result = prime * result + ((root == null) ? 0 : root.hashCode());
		return result;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj) {
			return true;
		}
		if (obj == null) {
			return false;
		}
		if (!(obj instanceof AbstractBinaryTree)) {
			return false;
		}
		AbstractBinaryTree other = (AbstractBinaryTree) obj;
		if (algoId != other.algoId) {
			return false;
		}
		if (ensureHashConsistency != other.ensureHashConsistency) {
			return false;
		}
		if (hashCount != other.hashCount) {
			return false;
		}
		if (root == null) {
			if (other.root != null) {
				return false;
			}
		} else if (!root.equals(other.root)) {
			return false;
		}
		return true;
	}

}
